Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра СКС
/
Звіт
з лабораторної роботи № 2
з дисципліни: “Дискретна математика”
на тему: “Задача про кістякове дерево екстремальної ваги”
Теоретичні відомості
При знаходженні кістякового дерева графа підхід із відкиданням ребер не є ефективним через те, що складно перевіряти наявність циклів в утворюваному графі.
Ефективним є підхід із конструюванням (утворенням) кістяка. У цьому разі просто перевіряти наявність циклів в графі, що виникає.
Вказаний підхід реалізує алгоритм Пріма (так званий алгоритм найближчого сусіда).
Крок 1. Присвоєння початкових значень.
S'={Xα}, Xα - довільна вершина графа (скажімо, перша за номером).
S''= S\S', V' = Ø
Крок 2. Оновлення даних.
Знаходимо таке ребро (Xi, Xj), що Xi ϵ S', Xj ϵ S'' та
W(Xi, Xj)= min{ W(Xα, Xβ)| Xα ϵ S', Xβ ϵ S''}
Покладаємо S' = S' U { Xi }, S'' = S\S', V' = V'U{(Xi, Xj)}
Крок 3. Перевірка на завершення.
Якщо S' = S, то G' = (S', V') - шуканий граф.
В іншому випадку переходимо на Крок 2.
Далі наведено приклад виконання алгоритму Пріма.
Граф задано списком ребер з вказанням їх ваг.
(1,4|1), (4,1|1), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,4|5),
(4,2|5), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (4,5|2), (5,4|2).
Відповідний цьому списку граф
/
Спершу впорядковуємо ребра за зростанням їх ваг. Для цього слід використати якийсь алгоритм сортування.
(1,4|1), (4,1|1), (4,5|2), (5,4|2), (1,5|3), (5,1|3), (2,3|3),
(3,2|3), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (2,4|5), (4,2|5).
Тепер власне виконуємо алгоритм Пріма (додаючи для кожного кроку 2 ребро мінімальної ваги).
S = {1,2,3,4,5}
Крок 1. S' = {1} S'' = {2,3,4,5} V' = Ø
Крок 2 . V' = V'U{(1,4|1)}={(1,4|1)}
S' = {1,4} S'' = {2,3,5}
Крок 3. S'≠S
Крок 2. V' = V'U{4,5|2} = {(1,4|1), (4,5|2)}
Крок 3. S'≠S
Крок 2. V' = V'U {(5,2|4)} = {(1,4|1), (4,5|2), (5,2|4)}
S' = {1,2,4,5} S'' = {3}
Крок 3. S'≠S
Крок 2. V' = V'U {(2,3|3)} = {(1,4|1), (4,5|2), (5,2|4), (2,3|3)}
S' = {1,2,3,4,5} S'' = Ø
Крок 3. S'=S
Таким чином, отримали таке кістякове дерево мінімальної ваги для початкового графа.
/
Вага отриманого кістякового дерева дорівнює 10.
Індивідуальне завдання
Знайти мінімальну вагу кістякового дерева.
Результат виконання програми
/
